﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Harmonogramowanie
{
    public class ScheduleCore
    {

        static public int[] TopOrder(CGraph G)
        {
            int[] LP = new int[G.n + 1];
            int[] ORD = new int[G.n + 1];

            for (int i = 1; i <= G.n; i++) LP[i] = G.Pred(i).Count;
            Queue<int> Q = new Queue<int>();
            for (int i = 1; i <= G.n; i++) if (LP[i] == 0) Q.Enqueue(i);
            int l = 0;
            while (Q.Count > 0)
            {
                int w = Q.Dequeue();
                ORD[++l] = w;
                foreach (int ns in G.Succ(w))
                    if (--LP[ns] == 0) Q.Enqueue(ns);
            }
            if (l < G.n) ORD[0] = -1; else ORD[0] = 0;
            return ORD;
        }


        public static int[] TopOrder(CGraph G, SetPer pi)
        {
            int[] LP = new int[G.n + 1];
            int[] ORD = new int[G.n + 1];
            for (int i = 1; i <= G.n; i++) LP[i] = G.Pred(i).Count;
            for (int i = 1; i <= pi.size; i++) if (pi.pi[i - 1] != 0) LP[pi.pi[i]]++;
            Queue<int> Q = new Queue<int>();
            for (int i = 1; i <= G.n; i++) if (LP[i] == 0) Q.Enqueue(i);
            int l = 0;
            while (Q.Count > 0)
            {
                int w = Q.Dequeue();
                ORD[++l] = w;
                foreach (int ns in G.Succ(w))
                    if (--LP[ns] == 0) Q.Enqueue(ns);
                int nsp = pi.pi[pi.ps[w] + 1];
                if (nsp != 0) if (--LP[nsp] == 0) Q.Enqueue(nsp);
            }
            if (l < G.n) ORD[0] = -1; else ORD[0] = 0;
            return ORD;
        }

        // S - czas rozpoczęcia
        // C - czas zakończenia
        // PH - ścieżka krytyczna

        static public int CALCULATE_HARM(CGraph G, SetPer pi, int[] TopOrder, int[] S, int[] C, int[] PH)
        {
            for (int i = 1; i <= G.n; i++) PH[i] = 0;
            for (int i = 1; i <= G.n; i++)
            {
                int w = TopOrder[i], s = 0;
                foreach (int p in G.Pred(w))
                    if (s < C[p]) { s = C[p]; PH[w] = p; }
                int pp = pi.pi[pi.ps[w] - 1];
                if (pp != 0) if (s < C[pp]) { s = C[pp]; PH[w] = pp; }
                S[w] = s; C[w] = s + G.Weights[w];
            }
            PH[0] = 1; for (int i = 1; i <= G.n; i++)
                if (C[PH[0]] < C[i]) PH[0] = i; ;
            return C[PH[0]];
        }



    }
}
